<html>
    <head>
        <meta charset="utf-8">
        <title>Leetcode 算法 －4. Median of Two Sorted Arrays</title>
        <link rel="stylesheet" href="../assets/stylesheets/global.css">
        <link rel="stylesheet" href="../assets/stylesheets/words.css">
        <link rel="stylesheet" href="../assets/stylesheets/monokai.css">
        <link rel="stylesheet" href="../assets/stylesheets/table.css">
        <link rel="shortcut icon" href="../assets/images/favicon.ico" type="image/x-icon">
        <link rel="icon" href="../assets/images/favicon.ico" type="image/x-icon">
        <script>
            // 统计代码
            (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
                (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
                m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
                })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

            ga('create', 'UA-93231524-1', 'auto');
            ga('send', 'pageview');
        </script>
    </head>
    <body>
        <div id="header">
            <a href="../index.html"><div id="logo">JG</div></a>
        </div>
        <div id="container" class="typo">
            <div id="article">
                <h1>Leetcode 算法 －4. Median of Two Sorted Arrays</h1>
                <h4>Posted August 17, 2016</h4>

                <blockquote class="blockquote-normal">
                <p><strong>问题链接</strong>: <a href="https://leetcode.com/problems/median-of-two-sorted-arrays/">4. Median of Two Sorted Arrays</a></p><br/><p><strong>问题描述</strong>: There are two sorted arrays nums1 and nums2 of size m and n respectively.<br/>Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).</p></blockquote>
<p><code>Example 1:</code></p>
<div class="code-wrapper"><span class="lang-label">Python</span><div class="highlight"><pre><span></span><span class="n">nums1</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">3</span><span class="p">]</span>
<span class="n">nums2</span> <span class="o">=</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span>

<span class="n">The</span> <span class="n">median</span> <span class="ow">is</span> <span class="mf">2.0</span>
</pre></div>
</div>
<p><code>Example 2:</code></p>
<div class="code-wrapper"><span class="lang-label">Python</span><div class="highlight"><pre><span></span><span class="n">nums1</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">]</span>
<span class="n">nums2</span> <span class="o">=</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">]</span>

<span class="n">The</span> <span class="n">median</span> <span class="ow">is</span> <span class="p">(</span><span class="mi">2</span> <span class="o">+</span> <span class="mi">3</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span> <span class="o">=</span> <span class="mf">2.5</span>
</pre></div>
</div><blockquote class="blockquote-normal">
                <p><strong>使用语言</strong>: Python</p></blockquote>
<p>解题思路:  先把列表碾平 , 由于两个列表元素类型相同直接相加即可. 然后排序. 计算中间位置, 可以通过判断奇偶数来分别处理开始index和结束index. 如果长度为奇数则直接返回最中间的， 如果为偶数则返回一个长度为2的list. 计算后返回. <strong>注意:</strong> 计算要使用float类型.</p>
<div class="code-wrapper"><span class="lang-label">Python</span><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">Solution</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">findMedianSortedArrays</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">nums1</span><span class="p">,</span> <span class="n">nums2</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        :type nums1: List[int]</span>
<span class="sd">        :type nums2: List[int]</span>
<span class="sd">        :rtype: float</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="n">nums</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="n">nums1</span> <span class="o">+</span> <span class="n">nums2</span><span class="p">)</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span> <span class="o">%</span> <span class="mi">2</span><span class="p">:</span>
            <span class="n">s</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">s</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span> <span class="o">-</span> <span class="mi">1</span>

        <span class="n">e</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">nums</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span>

        <span class="n">rs</span> <span class="o">=</span> <span class="n">nums</span><span class="p">[</span><span class="n">s</span><span class="p">:</span><span class="n">e</span><span class="p">]</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">rs</span><span class="p">)</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">rs</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">return</span> <span class="nb">sum</span><span class="p">(</span><span class="n">rs</span><span class="p">)</span> <span class="o">/</span> <span class="nb">float</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span>
</pre></div>
</div>
            </div>
            <div id="footer">
                <a href="../words.html"><div id="more-words">MORE WORDS</div></a>
            </div>
        </div>
    </body>
</html>